/*
 * @lc app=leetcode.cn id=19 lang=cpp
 *
 * [19] 删除链表的倒数第 N 个结点
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
// #include <iostream>
// using namespace std;
// struct ListNode {
//     int val;
//     ListNode* next;
//     ListNode() : val(0), next(nullptr) {}
//     ListNode(int x) : val(x), next(nullptr) {}
//     ListNode(int x, ListNode* next) : val(x), next(next) {}
// };

class Solution {
   public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 定义快慢指针
        ListNode* fast = head;
        ListNode* slow = head;

        // 先让快指针移动 n 个节点
        for (int i = 0; i < n; i++) {
            fast = fast->next;
        }

        // 如果快指针已经是nullptr，说明第一个节点就是要删除的节点
        // 如果不是，就让快指针和满指针同步移动
        if (fast == nullptr) {
            return head->next;
        }
        while (fast->next != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }

        // 此时慢指针所在的下一节点就是要删除的节点
        slow->next = slow->next->next;

        return head;
    }
};
// @lc code=end
